#include "main/utils.h"
using namespace std;

struct ListNode {
  int value;
  ListNode* pre;
  ListNode* next;
  ListNode* child;
};

ListNode* CreateListNode(int value) {
  ListNode* ret = new ListNode();
  ret->value = value;
  ret->pre = nullptr;
  ret->next = nullptr;
  ret->child = nullptr;
  return ret;
}

void ConnectNode(ListNode* node1, ListNode* node2) {
  node1->next = node2;
  node2->pre = node1;
}

ListNode* CreateList() {
  ListNode* node1 = CreateListNode(1);
  ListNode* node2 = CreateListNode(2);
  ListNode* node3 = CreateListNode(3);
  ListNode* node4 = CreateListNode(4);
  ListNode* node5 = CreateListNode(5);
  ListNode* node6 = CreateListNode(6);
  ListNode* node7 = CreateListNode(7);
  ListNode* node8 = CreateListNode(8);
  ListNode* node9 = CreateListNode(9);

  ConnectNode(node1, node2);
  ConnectNode(node2, node3);
  ConnectNode(node3, node4);
  ConnectNode(node5, node6);
  ConnectNode(node6, node7);
  ConnectNode(node8, node9);

  node2->child = node5;
  node6->child = node8;

  return node1;
}

void PrintLineList(ListNode* head) {
  ListNode* tail = nullptr;
  while (head) {
    cout << head->value << " ";
    if (head->next == nullptr) {
      tail = head;
    }
    head = head->next;
  }
  cout << endl;

  while (tail) {
    cout << tail->value << " ";
    tail = tail->pre;
  }
  cout << endl;
}

void PrintList(ListNode* head) {
  PrintLineList(head);
  while (head) {
    if (head->child) {
      cout << "===============" << endl;
      PrintList(head->child);
    }
    head = head->next;
  }
}

void flattenListCore(ListNode* node) {
  if (!node->child) {
    return;
  }
  auto next_node = node->next;
  auto child_node = node->child;
  node->next = child_node;
  child_node->pre = node;
  node->child = nullptr;
  ListNode* tail_node = nullptr;
  while (child_node) {
    if (child_node->next == nullptr) {
      tail_node = child_node;
    }
    child_node = child_node->next;
  }
  tail_node->next = next_node;
  if (next_node)
    next_node->pre = tail_node;
}

void flattenList(ListNode* head) {
  while (head) {
    flattenListCore(head);
    head = head->next;
  }
}

int main() {
  auto head = CreateList();
  flattenList(head);
  PrintList(head);

  return 0;
}
